/*--- lquick1.c --------------------------- Listing 5-17 --------
 * Quicksort for linked lists. Uses an insertion
 * sort on small subfiles and eliminates tail
 * recursion to minimize stack usage.
 *
 * Uses InsertionSortLink() from linsert.c (Listing 5-16)
 *
 * Adapted from an article by Jeff Taylor in
 * C Gazette, Vol 5, No. 6, 1991.
 *
 * #define DRIVER to compile a test driver
 * Driver must be linked to lsortsub.c (Listing 5-13)
 *-------------------------------------------------------------*/

#include "lsorthdr.h"

#define DRIVER 1

static CompFunc StoredCompare;
void InsertionSortLink ( Node **, Node *, CompFunc );

static void xQuickSortL1 ( Node **Head, Node *End )
{
    int left_count, right_count, count;
    Node **left_walk, *pivot, *old;
    Node **right_walk, *right;

    if ( *Head != End )
    do {
        pivot = *Head;       /* Take first element as pivot */
        left_walk = Head;    /* Set up left & right halves */
        right_walk = &right;
        left_count = right_count = 0;

        /* Now, walk the list */
        for ( old = (*Head)->next; old != End; old = old->next )
        {
            if ( StoredCompare ( old, pivot ) < 0 )
            {
                /* Less than pivot, so goes on left */
                left_count += 1;
                *left_walk = old;
                left_walk = &(old->next);
            }
            else
            {
                /* greater than or equal, so goes on right */
                right_count += 1;
                *right_walk = old;
                right_walk = &(old->next);
            }
        }

        /* Now glue the halves together... */
        *right_walk = End;   /* Terminate right list */
        *left_walk = pivot;  /* Put pivot after things on left */
        pivot->next = right; /* And right list after that */

        /* Now sort the halves in more detail */
        if ( left_count > right_count )
        {
            /*
             * Recursively sort (smaller) right half and then
             * reset local pointers so that when we loop, we
             * will see the left half as the entire list. Also,
             * if the right half has fewer than 10 elements,
             * sort it by insertion rather than by quicksort.
             */
            if ( right_count >= 9 )
                xQuickSortL1 ( &(pivot->next), End );
            else
                InsertionSortLink ( &(pivot->next), End,
                                    StoredCompare );
            End = pivot;
            count = left_count;
        }
        else
        {
            /* Converse case */
            if ( left_count >= 9 )
                xQuickSortL1 ( Head, pivot );
            else
                InsertionSortLink ( Head, pivot, StoredCompare );
            Head = &(pivot->next);
            count = right_count;
        }
    }
    while ( count > 1 );    /* end of do-while */
}

void QuickSortLink ( Node **Head, Node *End, CompFunc Compare )
{

    /* Save address of comparison function */
    StoredCompare = Compare;

    /* Quicksort the list */
    xQuickSortL1 ( Head, End );
}

#ifdef DRIVER
#include <stdio.h>
#include <string.h>
#include "lsortsub.h"

/*
 * A comparison function
 */
int Cfunc ( Node *L, Node *R )
{
    return ( strncmp ( L->text, R->text, 5 ));
}

void main ( int argc, char *argv[] )
{
    Node *ListHead;

    if ( argc != 2 )
    {
        fprintf ( stderr, "Usage: lquick1 infile\n" );
        return;
    }

    if ( LoadList ( argv[1], &ListHead ) == -1 )
        return; /* Couldn't load file */

    QuickSortLink ( &ListHead, NULL, (CompFunc) Cfunc );
    ShowArray ( ListHead, (CompFunc) Cfunc );
}
#endif
